package leetcode;

import Tree.BinaryTreeCreate;
import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class DeleteNodeInBST {

	public static void main(String[] args) {
		DeleteNodeInBST object = new DeleteNodeInBST();
		int[] pre = {5, 3, 2, 4, 6, 7};
		int[] in = {2, 3, 4, 5, 6, 7};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		root = object.deleteNode(root, 5);
		BinaryTreeCreate.preOrder(root);
		System.out.println();
		BinaryTreeCreate.inOrder(root);
	}
	
	public TreeNode deleteNode(TreeNode root, int key) {
		TreeNode fake = new TreeNode(Integer.MAX_VALUE);
		fake.left = root;
		TreeNode target = findNode(fake, key);
		if (target == null) {
			return root;
		}
		TreeNode del = null;
		
		TreeNode pre = null;
		TreeNode temp = null;
		boolean isLeft = true;
		// 但是此时我们不知道到底左结点还是右结点是啊，所以还需要判断
		if (target.left != null && target.left.val == key) {
			//找到左子树的最右结点
			del = target.left;
		} else {
			del = target.right;
			isLeft = false;
		}
		temp = del.left;
		while(temp != null && temp.right != null){
			pre = temp;
			temp = temp.right;
		}
		if(temp == null){
			//被删除结点没有左结点
			if(isLeft){
				target.left = del.right;
			}else{
				target.right = del.right;
			}
		}else if(pre == null){
			//没有右结点
			if(isLeft){
				target.left = temp;
			}else{
				target.right = temp;
			}
			temp.right = del.right;
		}else{
			pre.right = temp.left;
			temp.left = del.left;
			temp.right = del.right;
			if(isLeft){
				target.left = temp;
			}else{
				target.right = temp;
			}
		}
		return fake.left;
	}

	// 找到该结点的父节点
	public TreeNode findNode(TreeNode root, int key) {
		if (root == null) {
			return null;
		}
		TreeNode res = null;
		
		if(root.val > key){
			if (root.left != null) {
				if (root.left.val == key) {
					return root;
				}
				res = findNode(root.left, key);
			}
		}else if(root.val != key){
			if (root.right != null) {
				if (root.right.val == key) {
					return root;
				}
				res = findNode(root.right, key);
			}
		}
		return res;
	}
}
